ABSTRACT: Informatics (Computer Science) has changed the world and will continue to change it. Information technology affects all aspects of our lives; how we communicate, work, search, play, produce, manage, etc. Algorithms and data structures are the core of any computer system.

Algorithms and their implementation as programs should be correct and efficient, i.e., they should actually solve the problem they are supposed to solve and do so in short time. Incorrect algorithms can cause considerable damage, inefficient algorithms only cost money. In this talk, I will introduce the audience to the design and analysis of efficient algorithms and techniques for converting algorithms into correct programs. I will also discuss universal laws governing computation.

I hope that my talk with provide the audience with a sense of the intellectual depth, beauty, and fascination of Informatics.

---

CITATION

Computer Science has changed the world and will continue to change it. ALGORITHMS are at the core of every computer system. Kurt Mehlhorn is Europe’s ‘Mr. Algorithm’. His work has shaped Computer Science.

Mehlhorn has made fundamental contributions to algorithm science; data structures, computational geometry and algebra, parallel computing, VLSI design, complexity theory, combinatorial optimization and graph algorithms. His breadth is unrivalled. Algorithms, or more precisely, implementation of algorithms in the form of programs are at the core of every computer system. Programs have to be efficient and correct (accuracy and speed of completion). These two aspects are traditionally addressed by different communities within Computer Science. Mehlhorn has brought the two together through his pioneering work with Stefan Näher in the LEDA (Library of Implementations of Efficient Data Structures and Algorithms) project (since 1989). LEDA has spawned a revolutionary development and many subsequent libraries such as the Computational Geometry Algorithms Library (CGAL) and STXXL (Standard Template Library for Very Large Data Sets). These inventions have facilitated access by outside user communities; e.g. Celera Genomics software for human genome sequencing was based on LEDA.

---

BIOGRAPHICAL NOTE (http://www.mpi-inf.mpg.de/~mehlhorn/index.html)#

Kurt Mehlhorn earned his PhD in Computer Science from Cornell University in 1974 (Thesis: ‘Polynomial and Abstract Subrecursive Classes’). Since 1975, Member of Faculty, Saarland University, Saarbrücken, Germany. Since 1990, Director at the Max Planck Institute for Computer Science (MPII), Saarbrücken. Awarded the Gottfried Wilhelm Leibniz Prize (1986), the Karl Heinz Beckurts Award (1994), the Konrad Zuse Medal (1995), the EATCS Award (2010), and the ACM Paris Kanellakis Theory and Practice Award (2011). Named a Fellow of the Association of Computing Machinery (1999), a Member of the Berlin-Brandenburg Academy of Sciences (2001), a Member of the German Academy of Sciences Leopoldina (2004), and a Foreign Associate of the United States Academy of Engineering (2014). He received honorary doctorates from the Otto von Guericke University, Magdeburg (2002), the Aarhus University (2008), and the University of Waterloo (2006). Mehlhorn authored several books and over 250 scientific publications which include fundamental contributions to computational geometry, computer algebra, parallel computing, VLSI design, computational complexity, combinatorial optimization, and graph algorithms. He has also been an important figure in the development of algorithm engineering and is one of the developers of the Library of Efficient Data types and Algorithms (LEDA). Moreover, he played a central role in establishing research centres for computer science in Germany; most notably, the Max Planck Institute for Computer Science (MPII). Mehlhorn was Vice President of the Max Planck Society from 2002 to 2008.

ACADEMIA EUROPAEA MEMBERSHIP

TOP FIVE PUBLICATIONS IN THE PAST FIVE YEARS#

[1] Vincenzo Bonifaci, Kurt Mehlhorn, and Girish Varma: Physarum Can Compute Shortest Paths. Journal of Theoretical Biology, 309(0): 121-133, 2012.
[2] Kurt Mehlhorn and Michael Sagraloff: A Deterministic Descartes Algorithm for Real Polynomials. Journal of Symbolic Computation, 46(1): 70-90, 2011. [3] E. Alkassar, S. Böhme, K. Mehlhorn, and Ch. Rizkallah: A Framework for the Verification of Certifying Computations. Journal of Automated Reasoning (JAR), 52(3): 241-273, 2014. [4] R.M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer: Certifying Algorithms. Computer Science Review, 5(2): 119-161, 2011.
[5] Ran Duan and Kurt Mehlhorn: A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. Algorithmica (to appear).

URL for an online biography or home page: http://www.mpi-inf.mpg.de/~mehlhorn

---

Heinz Nixdorf Stiftung is - together with Stiftung Westfalen - one of the two non profit foundations, which have been established from the assets of the estate of the entrepreneur Heinz Nixdorf, who died in 1986. The foundation promotes the following purposes:

a) the (advanced) professional education, especially in the field of modern technology
b) the sciences in respect of research and teaching, especially in the field of information technology,
c) the liberal and democratic governmental system, especially the "Soziale Marktwirtschaft"
d) public health,
e) sports.

The foundation realizes its purposes primarily in cooperation with other non profit institutions.

Heinz Nixdorf MuseumsForum is the largest computer museum of the world.

Further information about the Heinz-Nixdorf Stiftung can be found at http://www.heinz-nixdorf-stiftung.de#

---

DOCUMENTS

• Award Announcement
• Press release